#include <stdio.h>
#include <conio.h>
#include <stdlib.h>
struct stack	{
	char dat;
	struct stack *next;
};
typedef struct stack Stack;
Stack *top,*t;

void push(char dat)
{
	t=(Stack *)malloc(sizeof(Stack));
	t->dat=dat;
	t->next=top;
	top=t;
}

char pop()
{
	int dat;
	dat=top->dat;
	t=top;
	if(t==NULL)	{
		printf("\nStack empty. Cannot pop");
		return NULL;
	}
	top=top->next;
	free(t);
	return dat;
}

void display()
{
	printf("\nStack:");
	t=top;
	while(t)	{
		printf("\n--%c",t->dat);
		t=t->next;
	}
}

int empty()
{
	if(top==NULL)
		return 1;
	else
		return 0;
}

void main()
{
	int i,j;
	char in[50]={0},post[50]={0},op;
	clrscr();
	printf("\nEnter infix:");
	gets(in);
	for(i=0,j=0;in[i]!=NULL;i++)	{
		switch(in[i])	{
			case '+':
			case '-':
				if(empty())	{
					push(in[i]);
				} else	{
					op=pop();
					while(op=='*' || op=='/')	{
						post[j]=op;
						j++;
						if(empty())
							break;
						op=pop();
					}
					if(op=='(')
						push(op);
					push(in[i]);
				}
				break;
			case '*':
			case '/':
				if(empty())	{
					push(in[i]);
				} else	{
					op=pop();
					while(op=='*' || op=='/')	{
						post[j]=op;
						j++;
						if(empty())
							break;
						op=pop();
					}
					if(op=='(' || op=='+' || op=='-')
						push(op);
					push(in[i]);
				}
				break;
			case '(':
				push(in[i]);
				break;
			case ')':
				op=pop();
				while(op!='(' && !empty())	{
					post[j]=op;
					j++;
					op=pop();
				}
				break;
			default:
				post[j]=in[i];
				j++;
		}
	}
	while(!empty())	{
		op=pop();
		if(op!='(')	{
			post[j]=op;
			j++;
		}
	}
	printf("Postfix:%s",post);
	getch();
}